0795. 区间子数组个数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 计数

1. 📝 题目描述

• leetcode

给你一个整数数组 nums 和两个整数：left 及 right。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

---

示例 1：

输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]

示例 2：

输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7

---

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= left <= right <= 10^9

2. 🎯 s.1 - 计数

c

int count(int* nums, int numsSize, int bound) {
    int res = 0, cur = 0;
    for (int i = 0; i < numsSize; i++) {
        cur = nums[i] <= bound ? cur + 1 : 0;
        res += cur;
    }
    return res;
}

int numSubarrayBoundedMax(int* nums, int numsSize, int left, int right) {
    return count(nums, numsSize, right) - count(nums, numsSize, left - 1);
}

js

/**
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var numSubarrayBoundedMax = function (nums, left, right) {
  const count = (bound) => {
    let res = 0,
      cur = 0
    for (const num of nums) {
      cur = num <= bound ? cur + 1 : 0
      res += cur
    }
    return res
  }
  return count(right) - count(left - 1)
}

py

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        def count(bound: int) -> int:
            res = cur = 0
            for num in nums:
                cur = cur + 1 if num <= bound else 0
                res += cur
            return res
        return count(right) - count(left - 1)

• 时间复杂度：$O(n)$，其中 n 是数组长度
• 空间复杂度：$O(1)$

算法思路：

• 最大值在 [left, right] 范围内的子数组个数 = 最大值 <= right 的子数组数 - 最大值 <= left-1 的子数组数
• count(bound) 统计最大值 <= bound 的子数组个数，维护当前连续满足条件的长度累加